//package com.gitee.feizns.explore.data_structure.tree.cus.ttt;
//
//import com.gitee.feizns.explore.data_structure.tree.cus.PutRet;
//
//import java.util.Arrays;
//import java.util.Collection;
//import java.util.LinkedList;
//import java.util.Objects;
//import java.util.OptionalInt;
//import java.util.Queue;
//import java.util.Set;
//import java.util.Stack;
//import java.util.TreeSet;
//import java.util.function.BiConsumer;
//import java.util.function.Consumer;
//import java.util.stream.Collectors;
//
///**
// * @author feizns
// * @since 2019/11/27
// */
//public class TttImpl<K extends Comparable<K>, V> implements Ttt<K, V> {
//
//    private TTNode<K, V> root;
//
//    private int size;
//
//    public TTNode<K, V> getRoot() {
//        return root;
//    }
//
//    @Override
//    public int size() {
//        return size;
//    }
//
//    @Override
//    public V get(Object key) {
//        return get(root, (K) key);
//    }
//
//    private V get(TTNode<K, V> root, K k) {
//        if ( root != null ) {
//            Entry<K, V>[] entries = root.values();
//            for (int i = 0; i < entries.length; i++) {
//                int comp = k.compareTo(entries[i].getKey());
//                if ( comp == 0 )
//                    return entries[i].getValue();
//                else if ( comp < 0 )
//                    return get(root.nodes[i], k);
//            }
//
//            if ( k.compareTo(entries[entries.length - 1].getKey()) > 0 )
//                return get(root.nodes[entries.length], k);
//        }
//        return null;
//    }
//
//    @Override
//    public V put(K key, V value) {
//        if ( root != null ) {
//            PutRet<TTNode<K, V>, V> ret = put(root, key, value);
//            root = ret.node();
//            return ret.v();
//        }
//        root = new TTNode<>(new EntryImpl<>(key, value));
//        size++;
//        return null;
//    }
//
//    private PutRet<TTNode<K, V>, V> put(TTNode<K, V> root, K k, V v) {
//        Entry<K, V>[] entries = root.values();
//        int nextIndex = -1;
//        for (int i = 0; i < entries.length; i++) {
//            int comp = k.compareTo(entries[i].getKey());
//            if ( comp == 0 )
//                return new PutRet<>(null, entries[i].setValue(v));
//            else if ( comp < 0 ) {
//                nextIndex = i;
//                break;
//            }
//        }
//
//        if ( nextIndex == -1 && k.compareTo(entries[entries.length - 1].getKey()) > 0 )
//            nextIndex = entries.length;
//
//        if ( nextIndex == -1 || root.nodes[nextIndex] == null ) {
//            size++;
//            return new PutRet<>(root.merge(new EntryImpl<>(k, v)), null);
//        }
//
//        PutRet<TTNode<K, V>, V> ret = put(root.nodes[nextIndex], k, v);
//        TTNode<K, V> node = ret.node();
//        if ( node.height == root.height ) {
//            TTNode<K, V>[] nodes = node.nodes();
//            root.nodes[nextIndex] = nodes[0];
//            root.insert(nextIndex + 1, nodes[1]);
//            TTNode<K, V> merge = root.merge(node.entries[0]);
//            return new PutRet<>(merge, null);
//        }
//        root.nodes[nextIndex] = node;
//        return new PutRet<>(root, ret.v());
//    }
//
////    private TTNode<K, V> merge(TTNode<K, V> node, K k, V v) {
////        EntryImpl<K, V> entry = new EntryImpl<>(k, v);
////        Entry<K, V>[] values = node.values();
////        for (int i = 0; i < values.length; i++) {
////            int comp = entry.getKey().compareTo(values[i].getKey());
////            if ( comp < 0 ) {
////
////            }
////        }
////    }
//
//    @Override
//    public V remove(Object key) {
//        return null;
//    }
//
//    @Override
//    public void clear() {
//        root = null;
//        size = 0;
//    }
//
//    @Override
//    public Set<K> keySet() {
//        return entrySet().stream().map(Entry::getKey).collect(Collectors.toSet());
//    }
//
//    @Override
//    public Collection<V> values() {
//        return entrySet().stream().map(Entry::getValue).collect(Collectors.toList());
//    }
//
//    @Override
//    public Set<Entry<K, V>> entrySet() {
//        TreeSet<Entry<K, V>> entries = new TreeSet<>();
//        beforeEach((k, v) -> entries.add(new EntryImpl(k, v)));
//        return entries;
//    }
//
//    @Override
//    public void recursiveBeforeEach(BiConsumer<K, V> consumer) {
//        recursiveBeforeEach(root, consumer);
//    }
//
//    private void recursiveBeforeEach(TTNode<K, V> node, BiConsumer<K, V> consumer) {
//        if ( node != null ) {
//            node.forEach(consumer);
//            node.forEachNodes(n -> recursiveBeforeEach(n, consumer));
//        }
//    }
//
//    @Override
//    public void recursiveAfterEach(BiConsumer<K, V> consumer) {
//        recursiveAfterEach(root, consumer);
//    }
//
//    private void recursiveAfterEach(TTNode<K, V> node, BiConsumer<K, V> consumer) {
//        if ( node != null ) {
//            node.forEachNodes(n -> recursiveBeforeEach(n, consumer));
//            node.forEach(consumer);
//        }
//    }
//
//    @Override
//    public void recursiveSequenceTraversal(BiConsumer<K, V> consumer) {
//        Queue<TTNode<K, V>> queue = new LinkedList<>();
//        queue.add(root);
//        recursiveSequenceTraversal(queue, consumer);
//    }
//
//    public void recursiveSequenceTraversal(Queue<TTNode<K, V>> queue, BiConsumer<K, V> consumer) {
//        Queue<TTNode<K, V>> newQueue = new LinkedList<>();
//        while ( !queue.isEmpty() ) {
//            TTNode<K, V> node = queue.remove();
//            node.forEach(consumer);
//            node.forEachNodes(n -> newQueue.add(n));
//        }
//        if ( !newQueue.isEmpty() )
//            recursiveSequenceTraversal(newQueue, consumer);
//    }
//
//    @Override
//    public void beforeEach(BiConsumer<K, V> consumer) {
//        Stack<TTNode<K, V>> stack = new Stack<>();
//        while ( !stack.isEmpty() ) {
//            TTNode<K, V> node = stack.pop();
//            node.forEach(consumer);
//            node.reverseEachNodes(stack::push);
//        }
//    }
//
//    @Override
//    public void afterEach(BiConsumer<K, V> consumer) {
//        Stack<TTNode<K, V>> stack = new Stack<>();
//        Stack<TTNode<K, V>> tmpStack = new Stack<>();
//        while ( !stack.isEmpty() ) {
//            TTNode<K, V> node = stack.pop();
//            tmpStack.push(node);
//            node.forEachNodes(n -> tmpStack.add(n));
//        }
//
//        while ( !tmpStack.isEmpty() ) {
//            TTNode<K, V> node = tmpStack.pop();
//            node.forEach(consumer);
//        }
//    }
//
//    @Override
//    public void sequenceTraversal(BiConsumer<K, V> consumer) {
//        Queue<TTNode<K, V>> queue = new LinkedList<>();
//        queue.add(root);
//        while ( !queue.isEmpty() ) {
//            TTNode<K, V> node = queue.remove();
//            node.forEach(consumer);
//            node.forEachNodes(queue::add);
//        }
//    }
//
//    static class TTNode<K extends Comparable<K>, V> {
//
//        int height;
//
//        int size;
//
//        TTNode<K, V>[] nodes;
//
//        Entry<K, V>[] entries;
//
//        public TTNode() {
//            this.nodes = new TTNode[4];
//            this.entries = new Entry[3];
//            this.height = 1;
//        }
//
//        public TTNode(Entry<K, V> entry) {
//            this();
//            entries[0] = entry;
//            size++;
//        }
//
//        public TTNode(Entry<K, V> entry, TTNode<K, V> left, TTNode<K, V> right) {
//            this(entry);
//            nodes[0] = left;
//            nodes[1] = right;
//            resetHeight();
//        }
//
//        public void resetHeight() {
//            this.height = h();
//        }
//
//        private int h() {
//            TTNode<K, V>[] nodes = nodes();
//            OptionalInt max = Arrays.stream(nodes).mapToInt(n -> h(n)).max();
//            int h = max.orElse(0);
//            return h + 1;
//        }
//
//        private int h(TTNode<K, V> node) {
//            return node == null ? 0 : node.height;
//        }
//
//        public K max() {
//            Entry<K, V>[] values = values();
//            return values[values.length - 1].getKey();
//        }
//
//        public int size() {
//            return size;
//        }
//
//        public TTNode<K, V>[] nodes() {
//            return Arrays.stream(nodes).filter(Objects::nonNull).toArray(TTNode[]::new);
//        }
//
//        public void forEachNodes(Consumer<TTNode<K, V>> consumer) {
//            TTNode<K, V>[] nodes = nodes();
//            for (TTNode<K, V> ttNode : nodes)
//                consumer.accept(ttNode);
//        }
//
//        public void reverseEachNodes(Consumer<TTNode<K, V>> consumer) {
//            TTNode<K, V>[] nodes = nodes();
//            for (int i = nodes.length - 1; i >= 0; i--)
//                consumer.accept(nodes[i]);
//        }
//
//        public Entry<K, V>[] values() {
//            return Arrays.stream(entries).filter(Objects::nonNull).toArray(Entry[]::new);
//        }
//
//        public void forEach(BiConsumer<K, V> consumer) {
//            Entry<K, V>[] entries = values();
//            for (Entry<K, V> entry : entries)
//                consumer.accept(entry.getKey(), entry.getValue());
//        }
//
//        public TTNode<K, V> merge(Entry<K, V> entry) {
//            Entry<K, V>[] values = values();
//            for (int i = 0; i < values.length; i++) {
//                int comp = entry.getKey().compareTo(values[i].getKey());
//                if ( comp < 0 ) {
//                    System.arraycopy(entries, i, entries, i + 1, values.length - i);
//                    entries[i] = entry;
//                    size++;
//                    break;
//                }
//            }
//
//            if ( values.length == size )
//                entries[size++] = entry;
//
//            for (int i = 0; i < values.length; i++) {
//                if ( nodes[i] != null ) {
//                    int comp = nodes[i].max().compareTo(values[i].getKey());
//                    if ( comp > 0 ) {
//                        System.arraycopy(nodes, i, nodes, i + 1, nodes.length - i);
//                        nodes[i] = null;
//                    }
//                }
//            }
//
//            if ( size == 3 ) {
//                TTNode<K, V> left = new TTNode<>(entries[0], nodes[0], nodes[1]);
//                TTNode<K, V> right = new TTNode<>(entries[2], nodes[2], nodes[3]);
//                TTNode<K, V> node = new TTNode<>(entries[1], left, right);
//                return node;
//            }
//            return this;
//        }
//
//        public void insert(int i, TTNode<K, V> node) {
//            TTNode<K, V>[] nodes = nodes();
//            TTNode<K, V>[] newNode = new TTNode[4];
//            for (int j = 0; j < i; j++)
//                newNode[j] = nodes[j];
//            newNode[i] = node;
//            for (int j = i + 1; j < nodes.length; j++)
//                newNode[j] = nodes[j - 1];
//            this.nodes = newNode;
//        }
//
//    }
//
//    static class EntryImpl<K, V> implements Entry<K, V> {
//
//        K k;
//
//        V v;
//
//        public EntryImpl(K k, V v) {
//            this.k = k;
//            this.v = v;
//        }
//
//        @Override
//        public K getKey() {
//            return k;
//        }
//
//        @Override
//        public V getValue() {
//            return v;
//        }
//
//        @Override
//        public V setValue(V value) {
//            V old = v;
//            v = value;
//            return old;
//        }
//
//    }
//
//}
